package main

import "fmt"

func numIslands(grid [][]byte) int {
	var res int
	visited := make([][]bool, len(grid))
	for i := 0; i < len(grid); i++ {
		visited[i] = make([]bool, len(grid[0]))
	}
	for i := 0; i < len(grid); i++ {
		line := grid[i]
		for j := 0; j < len(line); j++ {
			if line[j] == '0' {
				continue
			}
			if visited[i][j] {
				continue
			}
			cnt := dfs(grid, i, j, visited)
			res += cnt
		}
	}
	return res
}

func dfs(grid [][]byte, row, col int, visited [][]bool) (cnt int) {
	if grid[row][col] == '0' {
		return
	}
	if !visited[row][col] {
		cnt++
		visited[row][col] = true
	}
	// 上
	if row-1 >= 0 {
		if !visited[row-1][col] {
			visited[row-1][col] = true
			cnt += dfs(grid, row-1, col, visited)
		}
	}
	// 下
	if row+1 < len(grid) {
		if !visited[row+1][col] {
			visited[row+1][col] = true
			cnt += dfs(grid, row+1, col, visited)
		}
	}
	// 左
	if col-1 >= 0 {
		if !visited[row][col-1] {
			visited[row][col-1] = true
			cnt += dfs(grid, row, col-1, visited)
		}
	}
	// 右
	if col+1 < len(grid[row]) {
		if !visited[row][col+1] {
			visited[row][col+1] = true
			cnt += dfs(grid, row, col+1, visited)
		}
	}
	return
}

func main() {
	grid := [][]byte{
		{'1', '1', '1', '1', '0'},
		{'1', '1', '0', '1', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '0', '0', '1'},
	}
	fmt.Println(numIslands(grid))
}
